1. Field of the Invention
The present invention relates to an information processing apparatus and an information processing method, and in particular to, but not limited to, a technique for processing/managing data elements that move in mutually opposite directions in two-way pipelines that include interconnected nodes.
2. Description of the Related Art
There are applications that compare respective data elements held in each node of two data streams having a plurality of nodes. One example involves a process of comparing the elements of a first data stream having a plurality of data on a round robin basis when determining whether the elements match at least one of the elements of a second data stream. With such an application, the first data stream that moves data elements in one direction and the second data stream that moves data elements in the other direction respectively compare their respective data elements. However, as will be discussed later, with data streams that move data elements in mutually opposite directions, there are cases where the comparison of data elements in the nodes does not operate correctly.
Japanese Patent No. 3588487 discloses a two-way pipeline technique (counterflow pipeline technique) whereby in two pipeline data streams that move data elements in mutually opposite directions, respective data elements are compared at each stage of the pipelines. This technique involves symmetrically handling two datasets to form a simple regular structure by providing an irregular dataflow in opposite directions along regular paths. As a result, complex bypass circuits particular to typical RISC processors are made redundant. With this technique, each stage in a pipeline only communicates with the stage before and the stage after that stage, without communicating directly via the aforementioned bypass circuit, and data elements pass through a number of stages before being used. This technique is thus characterized by minimizing data transmission delays.
Also, typical synchronized pipelines operate using an inter-stage handshake protocol. With such a handshake protocol, in the case where the reception side indicates to the transmission side that there is space for housing a new data element, and there is a usable data element, the transmission side transmits the data element after indicating to the reception side to acquire that data element. Consequently, with such a handshake protocol of typical synchronous pipelines, the transmission side determines when to transfer data, giving rise to the possibility of a “bubble (equivalent to a gap in the dataflow)” occurring and a resultant drop in efficiency. With this technique, an adjacent stage (in the same pipeline) mutually and symmetrically decides (with another pipeline) when the data element of a given stage can move to the next stage, realizing point-symmetrical communication (with the other pipeline).
Further, this conventional technique has a configuration for moving data elements at an irregular schedule, according to scheduled operations to be executed on data elements and specific stages through which data elements passes when sent. This configuration suppresses the problem of the comparison of data elements in the nodes not operating correctly in data streams that move data elements in mutually opposite directions.
In view of this, the case where the data element comparison of this application does not operate correctly will first be described in detail using FIG. 9. A portion of two pipeline circuits that move data elements in opposite directions to one another is shown in FIG. 9. A first pipeline on the lower side moves data elements from the left side in the figure, which is the “upstream side”, toward the right side in the figure, which is the “downstream side”. On the other hand, a second pipeline on the upper side moves data elements from the right side in the figure, which is the “upstream side”, toward the left side in the figure, which is the “downstream side”. (a) in FIG. 9 shows the case where the first pipeline is operating (data elements move) and the second pipeline is not operating (data elements do not move), which is the case where the aforementioned problem does not arise. (a−1) in FIG. 9 shows the state at time[T], (a−2) in FIG. 9 shows the state at time[T+1], which is a given fixed period after time[T], and (a−3) in FIG. 9 shows the state at time[T+2], which is further fixed period after time[T+1]. As a result, the first pipeline is operating, and data elements W, A(0), A(1), A(2), B and C held in pipeline stages move from the left side in the figure, which is the “upstream side”, to the right side in the figure, which is the “downstream side”. Here, A(0), A(1) and A(2) are only distinguished with parenthesized numbers to facilitate description, and are in fact equivalent data. Corresponding stages in the first pipeline and the second pipeline are connected to one another by a determination (comparison) circuit.
The determination result of each stage at time[T] in (a−1) in FIG. 9 will be as follows from the “downstream side” of the first pipeline. First, at the initial stage on the downstream side of the first pipeline, the determination (comparison) circuit returns a determination result of “false”, because the data elements W and A, on comparison, do not match. The determination (comparison) circuit also returns a determination result of “false” for the following stages, on comparison of the respective data elements A(0) and Z, A(1) and Y, and A(2) and X.
Next, after a period of time elapses, the data elements of the first pipeline move one stage to the “downstream side” at time[T+1] in (a−2) in FIG. 9. The determination result of each stage will be as follows in order from the “downstream side” of the first pipeline. First, the data elements A(0) and A are compared, and the determination (comparison) circuit returns a determination result of “true”. At the following stages, the determination (comparison) circuit returns a determination result of “false”, on comparison of the respective data elements A(1) and Z, A(2) and Y, and B and X.
After a further period of time has elapsed, the data elements of the first pipeline have moved one more stage to the “downstream side” at time[T+2] in (a−3) in FIG. 9. The determination result of each stage will be as follows in order from the “downstream side” of the first pipeline. First, the data elements A(1) and A are compared, and the determination (comparison) circuit returns a determination result of “true”. At the following stages, the determination (comparison) circuit returns a determination result of “false”, on comparison of the respective data elements A(2) and Z, B and Y, and C and X.
As described above, the data elements of the first pipeline move through the stages with the passage of time, with the data element A on the “upstream side” of the second pipeline being correctly compared with both of the data elements A(0) and A(1) of the first pipeline. Thus in the case where either the first pipeline or the second pipeline is operating, while the other pipeline is not operating, the comparison of data elements operates correctly.
Next, the case where both the first pipeline and the second pipeline are operating is shown in (b) in FIGS. 9. (b−1) to (b−3) in FIG. 9 show states at the same times as (a−1) to (a−3) in FIG. 9. Because the first pipeline operates similarly to (a) in FIG. 9, description thereof will be omitted. On the other hand, the second pipeline, different from (a) in FIG. 9, also moves the data elements X, Y, Z, A, B and C held in pipeline stages from the right side in the figure, or the “upstream side”, to the left side in the figure, or the “downstream side”.
Hereinafter, the determination result of the determination (comparison) circuit in each corresponding stage of the first pipeline and the second pipeline will be described, similarly to (a) in FIG. 9. The determination result of each stage at time[T] in (b−1) in FIG. 9 will be as follows from the “downstream side” of the first pipeline. First, the initial determination (comparison) circuit on the downstream side of the first pipeline returns a determination result of “false”, because the data elements W and A, on comparison, do not match. The determination (comparison) circuits also return a determination result of “false” in the following stages, on comparison of the respective data elements A(0) and Z, A(1) and Y, and A(2) and X.
Next, after a period of time elapses, the data elements of the first pipeline and the second pipeline respectively move one stage to the “downstream side” at time[T+1] in (b−2) in FIG. 9. The determination result of each stage will be as follows in order from the “downstream side” of the first pipeline. First, the determination (comparison) circuit compares the data elements A(0) and B, and returns a determination result of “false”. At the next stage, the determination (comparison) circuit compares the data elements A(1) and A, and returns a determination result of “true”. The determination (comparison) circuits also return a determination result of “false” at the following stages, on comparison of the respective data elements A(2) and Z, and B and Y.
Further, after a period of time elapses, the data elements of the first pipeline and the data elements of the second pipeline respectively move one stage to the “downstream side” at time[T+2] in (b−3) in FIG. 9. The determination result of each stage will be as follows in order from the “downstream side” of the first pipeline. First, the determination (comparison) circuit returns a determination result of “false” because the data elements A(1) and C, on comparison, do not match (A(1) was, however, determined to be “true” by the determination (comparison) circuit in (b−2) in FIG. 9). The determination (comparison) circuits also return a determination result of “false” in the following stages, on comparison of the respective data elements A(2) and B, B and A, and C and Z.
As described above, the data element A on the “upstream side” of the second pipeline and the data element A(1) of the first pipeline are compared, but the data elements A(0) and A(2) are not compared with the data element A of the second pipeline. For example, when the respective data elements of the first pipeline match at least one of the respective data elements of the second pipeline, a correct determination cannot be obtained in the processing of (b−1) to (b−3) in FIG. 9, in the case of determining that this matching data element of the first pipeline matches. This is due to the fact that the relative movement speed of both the first pipeline and the second pipeline is doubled, since both pipelines move in opposite directions.
In fact, between times[T] and [T+2], only the comparisons of the data elements W, A(0) and A(1) of the first pipeline are completed, in the case of (a) in FIG. 9. In contrast, the comparisons of the data elements W, A(0), A(1), A(2) and B of the first pipeline are completed in the case of (b) in FIG. 9. Thus, while the case of (b) in FIG. 9 shortens the determination time compared with the case of (a) in FIG. 9, omissions arise in the comparison of data elements.
As aforementioned, the technique disclosed in Japanese Patent No. 3588487 solves the above problem by moving data elements at an irregular schedule according to the operations scheduled to be executed on data elements and specific stages through which data elements pass when moving. Specifically, the stage status is monitored in each stage of the first pipeline and the second pipeline. In specific stages in the case where the above problem occurs, both stages of the two-way pipelines cease operating, and movement of the data elements of those specific stages is permitted after comparison is completed. This prevents related data elements in two-way pipelines passing before comparison is completed.
However, with the technique of Japanese Patent No. 3588487, since the operations of stopping, completing comparisons and moving data elements are performed in specific stages, data elements are repeatedly moved and stopped on an irregular basis even if one stage is focused on. Originally, in a system constituting pipeline processing using a plurality of processing modules, improvement in throughput efficiency can be achieved the more regular the processing in each node. Thus, with the technique of Japanese Patent No. 3588487, improvement in throughput resulting from employing a pipeline configuration is inhibited. Also, in the case of moving data in each of two pipelines, data end up missing one another in the case where control is performed so that the respective pipelines are synchronized with reference to the same clock (clock signal).